# coding: utf-8

from queue import PriorityQueue


class Edge:
    def __init__(self, id, w):
        self.id = id
        self.w = w

    def __lt__(self, other):
        return self.w > other.w

    def __str__(self):
        return "e%d=%.1f" % (self.id, self.w)


class Path:
    def __init__(self, no, edges):
        self.no = no
        self.edges = edges

    def getH(self):
        return sum([e.w for e in self.edges])

    def __lt__(self, other):
        return self.getH() > other.getH()

    def __str__(self):
        return "P%d={%s} H%d=%.1f" % (
            self.no,
            ",".join(["e%d" % e.id for e in self.edges]),
            self.no,
            self.getH(),
        )


pq = PriorityQueue()

e1 = Edge(1, 422)
e2 = Edge(2, 269)
e3 = Edge(3, 276)
e4 = Edge(4, 916)
e5 = Edge(5, 15)
e6 = Edge(6, 8.4)
e7 = Edge(7, 27.4)
e8 = Edge(8, 340)
e9 = Edge(9, 873)
e10 = Edge(10, 640)

p1 = Path(1, [e1, e2, e4, e10])
p2 = Path(2, [e1, e2, e5, e7, e9, e10])
p3 = Path(3, [e1, e3, e6, e7, e9, e10])
p4 = Path(4, [e1, e3, e8, e9, e10])

pq.put(p1)
pq.put(p2)
pq.put(p3)
pq.put(p4)
print(*pq.queue)

e5.w += 500
# trick: 强制更新pq
pq.put(pq.get())
print(*pq.queue)

print(pq.get())
# print(*pq.queue)
print(pq.get())
# print(*pq.queue)
print(pq.get())
print(pq.get())
# print(*pq.queue)
